n = int(input())
m = int(input())
ls = []
for _ in range(m+1):
    a,b = map(int,input().split())
    ls.append([a,b])

def bag(num, c, w, v):
    res = [[-1 for i in range(c + 1)] for j in range(n + 1)]
    for j in range(c + 1):
        res[0][j] = 0
    for i in range(1, num):
        for j in range(1, c):
            if j < w[i]:
                res[i][j] = res[i - 1][j]
            else:
                res[i][j] = max((res[i - 1][j], res[i - 1][j - w[i]] + v[i]))
    print(res[1:])
    return res

vm = list(map(list,zip(*ls)))
w = [0]+vm[0]
v = [0]+vm[1]
bag(m,n,w,v)